#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "btree.h"

int tree_init(tree_t **mytree, int size)
{
	*mytree = malloc(sizeof(tree_t));
	if (NULL == *mytree)
		return -1;
	(*mytree)->root = NULL;
	(*mytree)->size = size;
}

static struct node * __new_node(const void *data, int size)
{
	struct node *p = NULL;
	
	p = malloc(sizeof(struct node) + size);
	if (NULL == p)
		return NULL;
	p->left = p->right = NULL;
	memcpy(p->data, data, size);

	return p;
}

static int __insert(struct node **root, struct node *new_node, cmp_t cmp)
{
	if (NULL == *root) {
		// 空
		*root = new_node;
		return 0;
	}
	// 树不空
	if (cmp((*root)->data, new_node->data) >= 0) {
		return __insert(&(*root)->left, new_node, cmp);	
	} else {
		return __insert(&(*root)->right, new_node, cmp);	
	}
}

int tree_insert(tree_t *mytree, const void *data, cmp_t cmp)
{
	// 初始化一个新的结点
	struct node *ptr = __new_node(data, mytree->size);
	if (NULL == ptr)
		return -1;

	// 插入到树中
	__insert(&mytree->root, ptr, cmp);

	return 0;
}

// 找到指向匹配结点的指针的地址
static struct node **__find(struct node **root, const void *key, cmp_t cmp)
{
	int ret;

	if (*root == NULL)
		return NULL;
	ret = cmp((*root)->data, key);
	if (ret == 0)
		return root;
	else if (ret < 0) {
		return __find(&(*root)->right, key, cmp);	
	} else
		return __find(&(*root)->left, key, cmp);
}

static struct node *__find_max(struct node *root)
{
	if (root == NULL)
		return NULL;
	if (root->right == NULL)
		return root;
	return __find_max(root->right);
}

static int __delete(struct node **root)
{
	struct node *del = *root;	
	struct node *r = del->right;
	struct node *l = del->left;

	if (NULL != l) {
		*root = l;
		if (NULL != r) {
			// l树上最大结点的right指针指向r
			__find_max(l)->right = r;
		}
	} else {
		*root = r;
	}

	del->left = del->right = NULL;
	free(del);
	del = NULL;

	return 0;
}

int tree_delete(tree_t *mytree, const void *key, cmp_t cmp)
{
	// 找
	struct node **del = __find(&mytree->root, key, cmp);
	if (NULL == del)
		return -1;

	// 删
	__delete(del);

	return 0;
}

void *tree_find(const tree_t *mytree, const void *key, cmp_t cmp)
{
	struct node **f = __find(&((tree_t*)mytree)->root, key, cmp);
	if (NULL == f)
		return NULL;
	return (*f)->data;
}

static void __traval_mid(const struct node *root, pri_t pri)
{
	if (NULL == root)
		return ;
	__traval_mid(root->left, pri);
	pri(root->data);
	__traval_mid(root->right, pri);
}

void tree_traval_mid(const tree_t *mytree, pri_t pri)
{
	__traval_mid(mytree->root, pri);
}

static void __destroy(struct node **root)
{
	if (*root == NULL)
		return ;
	__destroy(&(*root)->left);
	__destroy(&(*root)->right);
	free(*root);
	*root = NULL;
}

void tree_destroy(tree_t **mytree)
{
	__destroy(&(*mytree)->root);

	free(*mytree);
	*mytree = NULL;
}

